package SortAlgorithm;

import java.util.Arrays;

public class MergeSort2 {
    public static void merge(int[] arr,int L,int mid, int R){
        int[] help=new int[arr.length];
        help= Arrays.copyOf(arr,arr.length);
        int cur=L;
        int left=L;
        int right=mid+1;
        while(left<=mid&&right<=R){
            if(help[left]<=help[right]){
                arr[cur++]=help[left++];
            }else{
                arr[cur++]=help[right]++;
            }
        }
        while(left<=mid){
            arr[cur++]=help[left++];
        }
    }
    public static void mergeSort2(int[] array){
        int gap=1; //每组的数据
        while(gap<array.length){
            for(int i=0;i<array.length;){
                int s1=i;
                int e1=s1+gap-1;
                if(e1>=array.length){
                    e1=array.length-1;
                }
                int s2=e1+1;
                if(s2>=array.length){
                    s2=array.length-1;
                }
                int e2=s2+gap-1;
                if(e2>=array.length){
                    e2=array.length-1;
                }
                merge(array,s1,e2,e1);
            }
            gap*=2;
        }
    }
}
